package com.silence.ByteDance;

// 小 M 与弹子游戏机
public class easy_72 {
    public static int solution(int n, int m, int[][] array) {
        // Edit your code here
        // n 是高，m 是宽
        int max = 0;
        for (int j = 0; j < m; j++) {
            if (sm(n, m, 0, j, array) > max) {
                max = sm(n, m, 0, j, array);
            }
        }
        return max;
    }

    public static int sm(int n, int m, int i, int j, int[][] array) {
        if (i == n) return 0;
        if (i == n - 1) { // 最后一层
            return (array[i][j] == -1) ? 0 : array[i][j];
        }
        int next = 0;
        if (array[i][j] != -1) { // 垂直
            next += sm(n, m, i + 1, j, array) + array[i][j];
        } else {
            if (j == 0) { // 往右
                next = sm(n, m, i + 1, j + 1, array);
            } else if (j == m - 1) { // 往左
                next = sm(n, m, i + 1, j - 1, array);
            } else {
                next = Math.max(sm(n, m, i + 1, j + 1, array), sm(n, m, i + 1, j - 1, array));
            }
        }
        return next;
    }

    public static void main(String[] args) {
        // Add your test cases here
        System.out.println(solution(3, 3, new int[][]{
                {-1, 0, -1},
                {100, 0, 0},
                {0, 50, 70}}) == 50);
        System.out.println(solution(4, 3, new int[][]{
                {-1, 0, -1},
                {0, -1, 0},
                {50, 100, 70},
                {80, 200, 50}}) == 130);
        System.out.println(solution(5, 5, new int[][]{
                {-1, 0, -1, 0, -1},
                {0, -1, 0, -1, 0},
                {0, 10, 0, 20, 0},
                {-1, 0, -1, 0, -1},
                {0, 30, 0, 40, 0}}) == 40);
        System.out.println(solution(4, 4, new int[][]{
                {-1, -1, -1, -1},
                {-1, -1, -1, -1},
                {-1, -1, -1, -1},
                {-1, -1, -1, -1}}) == 0);
    }
}
